package com.zwh.se.collection.map;

import java.util.HashMap;

/**
 * @author yexi
 * 探讨HashMap底层的解释类。由于HashMap底层的内容过多,因此特地抽取出来讲。
 * 在JDK1.8 之前 HashMap 的底层实现仅为数组+链表(哈希表)。
 * 1.8之后为了能够在发生哈希冲突时保证检索的效率,在链表长度大于阈值(默认8)且数组长度不小于64时将转换成红黑树。
 * "拉链法"：哈希表借由数组+链表实现的前提。也就是当遇到哈希冲突时，将冲突的值与原位置的值通过链表连在一起。
 *
 * 一句话纯背：JDK1.8的HashMap的底层实现是哈希表,为了减少哈希冲突的影响,在哈希表的链表达成长度大于8且数组长度不小于64时,
 *          会先将链表转换为双向链表结构,然后再借由双向链表使其转换成红黑树结构。
 *
 * 先简单介绍一下红黑树的特点：
 * 1、每个节点是黑的或者红的
 * 2、根节点是黑色的
 * 3、如果一个节点是红的，则它的两个儿子都是黑的
 * 4、对于每个叶子节点，从该节点到根节点的所有路径上包含相同数目的黑色节点
 *
 * @link https://www.cs.usfca.edu/~galles/visualization/Algorithms.html  数据结构算法可视化网站
 */
@SuppressWarnings("all")
public class HashMapEssentially {
    public static void main(String[] args) {
        /**
         * 基本的也是最重要的几个属性：
         * @see HashMap#DEFAULT_INITIAL_CAPACITY  哈希表主数组的默认长度—16。必须是 2的n次幂。
         * @see HashMap#DEFAULT_LOAD_FACTOR 默认负载因子(装填因子/加载因子)值,默认值是0.75f。
         *        为什么是0.75呢?
         *        我们举个例子:如果是1,则更好地获得了空间利用率,但是也更容易发生哈希碰撞了(因为可能一直不扩容)。若产生链表,那么查询效率就会变低。
         *        如果是更小,比如0.5,虽然哈希碰撞的概率会变得很低,查询的效率变高了(相对),但是扩容却经常会发生了,导致空间的利用率变低了。
         *        而0.75是在空间和时间上所做的一个折中值,是行业前辈们经过大量测试后所敲定的最合适的值。
         * @see HashMap#table 底层用来存储的主数组Node。该数组会在首次使用时初始化,并可根据需要调整大小。其分配容量时,长度始终是 2的n次幂。
         *        为什么主数组的长度必须是2的n次幂?
         *        1、减少哈希冲突(其他数字在运算时更容易会出现哈希值相同的情况)
         *        2、可以保证 h & (length-1) 等效于 h % length
         * @see HashMap#size  主数组的容量
         * @see HashMap#threshold  数组扩容的界限值(阈值、门槛值)  由 数组长度*负载因子 算出(比如默认就是16*0.75=12)
         * @see HashMap#loadFactor 负载因子(装填因子)。表示哈希表中元素的填满的程度,简单来说就是当所需容量超过 数组长度*负载因子 时,才进行扩容。
         *          为什么要设计这么一个数字是为了减少哈希冲突。所谓哈希冲突,就是key所计算的hash值相同,导致了存储在了数组中的同一个位置,
         *          从而需要延伸出链表来进行存储,就会有一定的内存和寻址浪费。负载因子值可以修改,但不建议。
         * @see HashMap#MAXIMUM_CAPACITY  数组容量的界限值
         *
         * @see HashMap.Node 底层数组实际存储的元素(当触发转换红黑树之后会转变为TreeNode)
         * @see HashMap.Node#key Node元素存储的key值
         * @see HashMap.Node#value Node元素存储的value值
         * @see HashMap.Node#hash key值计算出来的hash值
         * @see HashMap.Node#next 下一个节点,也是存储的Node,通过该字段来实现链表。
         */
        //构造一个负载因子为0.75f,容量为16的数组。
        HashMap<String, String> hashMap = new HashMap<>(0);
        /**
         * 构造一个具有指定初始容量和默认加载因子 (0.75) 的空HashMap 。
         * initialCapacity:初始容量(然而并不是)
         * @see HashMap#HashMap(int initialCapacity, float loadFactor)
         *         this.loadFactor = loadFactor;
         *         this.threshold = tableSizeFor(initialCapacity);
         * @see HashMap#tableSizeFor(int initialCapacity) 将给定的初始容量转变为大于它的最小 2的n次幂 再返回(真正的初始容量)
         *         //该算法的实现目的是为了可以让底层二进制最高位的1的右侧全部变为1(则可以必然保证数字是2的n次幂)
         *         int n = cap - 1;
         *         n |= n >>> 1;
         *         n |= n >>> 2;
         *         n |= n >>> 4;
         *         n |= n >>> 8;
         *         n |= n >>> 16;
         *         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
         *
         * 所以下例实际做的：初始化一个数组容量为16、负载因子是0.75的空HashMap
         */
        hashMap = new HashMap<>(9);
        /**
         * @see HashMap#put(Object key, Object value)
         *        // hash(key) —— 计算key的hash值
         *         return putVal(hash(key), key, value, false, true);
         *
         * //JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。
         * @see HashMap#hash(Object key)
         *         int h;
         *         //简化了哈希值的计算方法，JDK 1.7 的 hash 方法进行了4次扰动,性能会稍差一点点。
         *         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
         *
         * @param onlyIfAbsent 如果为true，则不更改现有值
         * @param evict 如果为 false，代表表正处于创建模式。
         * @see HashMap#putVal(int hash, Object key, Object value, boolean onlyIfAbsent, boolean evict)
         *              Node<K,V>[] tab;  //底层数组
         *              Node<K,V> p;     // p = tab[i = (n - 1) & hash] : 获取到索引位的 Node 值
         *              int n, i;    //n是底层数组长度, i是通过哈希码计算出来的该值的索引位
         *         if ((tab = table) == null || (n = tab.length) == 0)
         *             //如果底层数组是null或者长度为0的话,则先对底层数组进行扩容,再将扩容后的数组长度赋值给n
         *             n = (tab = resize()).length;
         *         //如果在该索引位上取到的元素是null
         *         if ((p = tab[i = (n - 1) & hash]) == null)
         *             //则直接将元素加到数组的对应位置当中去
         *             tab[i] = newNode(hash, key, value, null);
         *         else {
         *             //如果索引位上已存在元素,则代表发生了哈希冲突,需要拉链法进行拉链
         *             Node<K,V> e; // Node节点,根据逻辑不同代表着不同的意思
         *             K k; // key值
         *             //与链表的表头元素进行比较,如果哈希值相同且(key值相同或者逻辑上相同)则认为是同一个key
         *             if (p.hash == hash &&
         *                 ((k = p.key) == key || (key != null && key.equals(k))))
         *                 e = p;
         *             else if (p instanceof TreeNode)
         *                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         *             //如果不是key重复且不是TreeNode的实例的情况下执行
         *             else {
         *                //从链表的头开始往下进行遍历,直至满足条件break为止
         *                // binCount:桶的个数(一般喜欢将链表里面的节点称之为"桶")
         *                 for (int binCount = 0; ; ++binCount) {
         *                     //因为已经跟表头元素比过了,所以找p的下一个节点元素接着比
         *                     //如果其已经没有下一个节点元素,则代表没有重复key的元素
         *                     if ((e = p.next) == null) {
         *                         //则新增元素作为其尾部元素新增进来(尾插法)
         *                         p.next = newNode(hash, key, value, null);
         *                         //如果链表遍历次数已经 >= TREEIFY_THRESHOLD(默认为8)-1 (也就是链表长度已经至少是8)
         *                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
         *                             //将链表转化为红黑树
         *                             treeifyBin(tab, hash);
         *                         break;
         *                     }
         *                     //在链表遍历时找到了key重复的Node
         *                     if (e.hash == hash &&
         *                         ((k = e.key) == key || (key != null && key.equals(k))))
         *                         break;
         *                     //下一个节点作为新的头节点来准备进行下一次遍历
         *                     p = e;
         *                 }
         *             }
         *             // 如果 e!=null,代表着此次操作出现了重复key的情况,执行覆盖旧值操作
         *             if (e != null) { // existing mapping for key
         *                 V oldValue = e.value;
         *                 //如果设定了更改旧值或者旧值是null的话,则使用新值覆盖旧值
         *                 if (!onlyIfAbsent || oldValue == null)
         *                     e.value = value;
         *                 afterNodeAccess(e);  //交由 LinkedHashMap 来实现
         *                 return oldValue;
         *             }
         *         }
         *         ++modCount;
         *         if (++size > threshold)  //如果容量即将超过阈值了
         *             resize();   //则扩容
         *         afterNodeInsertion(evict);  //交由 LinkedHashMap 来实现
         *         return null;
         *
         * //将给定的哈希索引位上的所有链表节点替换成红黑树结构,如果底层数组太小,则在这种情况下先扩容而非先转换链表
         * @see HashMap#treeifyBin(HashMap.Node[] tab, int hash)
         *         int n, index; //n是底层数组长度,index是通过hash计算出来的索引位
         *         Node<K,V> e;
         *         // 如果此时的底层数组是null或 数组长度<MIN_TREEIFY_CAPACITY(默认为64),则执行扩容,先放弃转换红黑树
         *         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         *             resize();
         *         // 如果该索引位上的元素不为null的话(健壮性考虑,就目前的逻辑执行下来的话看上去不需要)
         *         else if ((e = tab[index = (n - 1) & hash]) != null) {
         *             TreeNode<K,V> hd = null, tl = null;   //头部(head)、尾部(tail)
         *             //将原来的单向链表变为双向链表(TIPS:注意此时还没有真正地转化为红黑树结构)
         *             do {
         *                 //将Node节点转换为TreeNode节点
         * @see HashMap.TreeNode extends LinkedHashMap.Entry extends HashMap.Node  //所以TreeNode也拥有Node的所有属性
         * @see HashMap.TreeNode#parent  父节点
         * @see HashMap.TreeNode#left  左子树节点
         * @see HashMap.TreeNode#right 右子树节点
         * @see HashMap.TreeNode#prev  上一个节点(再借由原Node的next,实现了双向链表)
         * @see HashMap.TreeNode#red   是否是红色(false的话就是黑色)
         *                 TreeNode<K,V> p = replacementTreeNode(e, null);
         *                 //如果尾部元素是null(必然是原链表第一位元素才会触发该条件)
         *                 if (tl == null)
         *                     // 则将该索引位原来第一位的元素视作头节点
         *                     hd = p;
         *                 //除链表第一位元素之外,其他的情况都会到这个条件
         *                 else {
         *                     // 将原尾节点用作自己的上一个节点
         *                     p.prev = tl;
         *                     // 而自己则作为原尾节点的下一个节点
         *                     tl.next = p;
         *                 }
         *                 // 新来的元素就视作尾节点(如果是第一个元素即同时充当头节点和尾节点)
         *                 tl = p;
         *             } while ((e = e.next) != null);  //不断根据链表遍历下去,直至到链表的尾部
         *             //如果头节点不为null
         *             if ((tab[index] = hd) != null)
         *                 //将底层数组传入,将上面做好的双向链表重构成红黑树结构(注意该方法由双向链表的头节点来调用)
         *                 hd.treeify(tab);
         *         }
         *
         * @see HashMap#resize() 扩容机制：初始化或将表容量翻倍。如果为空,则按照字段阈值中保存的初始容量目标进行分配。
         *         Node<K,V>[] oldTab = table;  //底层数组(旧),必将被替换
         *         int oldCap = (oldTab == null) ? 0 : oldTab.length;  //如果是初始化,则设 旧容量 为0,否则取旧数组长度
         *         int oldThr = threshold;   //旧阈值
         *         int newCap, newThr = 0;  //新容量、新阈值
         *         //如果旧容量>0
         *         if (oldCap > 0) {
         *             //健壮性考虑
         *             if (oldCap >= MAXIMUM_CAPACITY) {
         *                 threshold = Integer.MAX_VALUE;
         *                 return oldTab;
         *             }
         *             // 新容量赋值为旧容量的2倍,且判断赋值后是否会超过MAXIMUM_CAPACITY(健壮性)
         *             // 同时判断旧容量是否 >= 默认初始容量
         *             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         *                      oldCap >= DEFAULT_INITIAL_CAPACITY)
         *                 //都满足的话,阈值也扩容为2倍
         *                 newThr = oldThr << 1; // double threshold
         *         }
         *         //如果旧容量不>0且旧阈值>0
         *         else if (oldThr > 0) // initial capacity was placed in threshold
         *             //旧阈值用作新容量
         *             newCap = oldThr;
         *         //如果旧容量和旧阈值均不大于0
         *         else {               // zero initial threshold signifies using defaults
         *             // 新容量赋值为默认初始容量
         *             newCap = DEFAULT_INITIAL_CAPACITY;
         *             // 新阈值赋值为默认阈值(默认负载因子*默认初始容量)
         *             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
         *         }
         *         // 如果新阈值==0(一般是走了 else if (oldThr > 0) 的代码块后才触发)
         *         if (newThr == 0) {
         *             // 使用新容量 * 负载因子
         *             float ft = (float)newCap * loadFactor;
         *             // 如果 新容量<最大容量且 算出来的值<最大容量 则 赋值给新阈值(健壮性)
         *             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
         *                       (int)ft : Integer.MAX_VALUE);
         *         }
         *         threshold = newThr;    //新阈值
         *         @SuppressWarnings({"rawtypes","unchecked"})
         *         Node<K, V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建一个新的Node数组
         *         table = newTab;   //新Node数组替换成为新的底层数组
         *         if (oldTab != null) {
         *            //遍历,将旧底层数组的元素一个个塞入到新底层数组当中
         *             for (int j = 0; j < oldCap; ++j) {
         *                 Node<K,V> e;
         *                 //如果该位置元素不为null
         *                 if ((e = oldTab[j]) != null) {
         *                     oldTab[j] = null;
         *                     //如果该位置元素的下一个元素是null(也就是它是链表的最后一个元素了)
         *                     if (e.next == null)
         *                         //直接塞到新数组当中
         *                         newTab[e.hash & (newCap - 1)] = e;
         *                     else if (e instanceof TreeNode)
         *                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
         *                     else { // preserve order
         *                         Node<K,V> loHead = null, loTail = null;
         *                         Node<K,V> hiHead = null, hiTail = null;
         *                         Node<K,V> next;
         *                         do {
         *                             next = e.next;
         *                             if ((e.hash & oldCap) == 0) {
         *                                 if (loTail == null)
         *                                     loHead = e;
         *                                 else
         *                                     loTail.next = e;
         *                                 loTail = e;
         *                             }
         *                             else {
         *                                 if (hiTail == null)
         *                                     hiHead = e;
         *                                 else
         *                                     hiTail.next = e;
         *                                 hiTail = e;
         *                             }
         *                         } while ((e = next) != null);
         *                         if (loTail != null) {
         *                             loTail.next = null;
         *                             newTab[j] = loHead;
         *                         }
         *                         if (hiTail != null) {
         *                             hiTail.next = null;
         *                             newTab[j + oldCap] = hiHead;
         *                         }
         *                     }
         *                 }
         *             }
         *         }
         *         return newTab;
         *
         * @see HashMap.TreeNode#treeify(HashMap.Node[] tab) //将底层数组的内部的双向链表转化为红黑树结构
         *             TreeNode<K,V> root = null;  //红黑树的根节点
         *             //由于该方法由TreeNode来调用,所以此时的this相当于是双向链表的头节点
         *             // 这部分遍历的是双向链表的每个元素
         *             for (TreeNode<K,V> x = this, next; x != null; x = next) {
         *                 next = (TreeNode<K,V>)x.next;  //获取下一个元素
         *                 x.left = x.right = null;  //左子树和右子树初始化为null
         *                 //如果根节点是null
         *                 if (root == null) {
         *                     //父节点置null(根节点不存在父节点)
         *                     x.parent = null;
         *                     //根节点是黑色
         *                     x.red = false;
         *                     //则当前元素充当根节点(也就是最开始的this,原双向链表的头节点)
         *                     root = x;
         *                 }
         *                 else {
         *                     K k = x.key;  //获取key值
         *                     int h = x.hash;  //获取hash值
         *                     Class<?> kc = null;
         *                     //从根节点开始循环遍历,满足break条件时才跳出循环(往红黑树里面加元素,需要计算其位置)
         *                     // 这个部分遍历的是已经做到一半的红黑树(因为要计算新元素要放到左子树还是右子树,以及还有左旋和右旋的问题)
         *                     for (TreeNode<K,V> p = root;;) {
         *                         int dir, ph;
         *                         K pk = p.key;  //获取key值
         *                         if ((ph = p.hash) > h)
         *                             dir = -1;
         *                         else if (ph < h)
         *                             dir = 1;
         *                         else if ((kc == null &&
         *                                   (kc = comparableClassFor(k)) == null) ||
         *                                  (dir = compareComparables(kc, k, pk)) == 0)
         *                             dir = tieBreakOrder(k, pk);
         *
         *                         TreeNode<K,V> xp = p;
         *                         if ((p = (dir <= 0) ? p.left : p.right) == null) {
         *                             x.parent = xp;
         *                             if (dir <= 0)
         *                                 xp.left = x;
         *                             else
         *                                 xp.right = x;
         *                             root = balanceInsertion(root, x);
         *                             break;
         *                         }
         *                     }
         *                 }
         *             }
         *             moveRootToFront(tab, root);
         *
         *
         */
        hashMap.put("1","a");

    }
}
